#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "linkedlist.h"


linkedlist::linkedlist() {
	first=NULL;
	last=NULL;
}
linkedlist::~linkedlist() {
	removeAll();
}
int linkedlist::cmp(struct list *a,struct list *b) {
	//printf("Comparing %s and %s\n",a->data,b->data);
	return (strcmp(a->data,b->data));
}
void linkedlist::regeneratebacklinks() {
	struct list *tmp,*prev;
	tmp=first;
	while (tmp!=NULL) {
		prev=tmp;
		tmp=tmp->next;
		if (tmp!=NULL)
			tmp->prev=prev;
	}
	last=prev;
}
void linkedlist::sort(){
    	//printf("Sorting Called\n");
	struct list *p, *q, *e, *tail;
    	int insize, nmerges, psize, qsize, i;
    	if (isEmpty()) 		// Empty
		return;

    	insize = 1;

    	while (true) {
        	p = first;
        	first = NULL;
        	tail = NULL;

        	nmerges = 0;  /* count number of merges we do in this pass */

        	while (p) {
            		nmerges++;  /* there exists a merge to be done */
            		/* step `insize' places along from p */
            		q = p;
            		psize = 0;
            		for (i = 0; i < insize; i++) {
                		psize++;
		    		q = q->next;
                		if (!q) break;
            		}

		        /* if q hasn't fallen off end, we have two lists to merge */
            		qsize = insize;

            		/* now we have two lists; merge them */
            		while (psize > 0 || (qsize > 0 && q)) {
                		/* decide whether next element of merge comes from p or q */
                		if (psize == 0) {
		    			/* p is empty; e must come from q. */
		    			e = q; q = q->next; qsize--;
				} else if (qsize == 0 || !q) {
		    			/* q is empty; e must come from p. */
		    			e = p; p = p->next; psize--;
				} else if (cmp(p,q) <= 0) {
		    			/* First element of p is lower (or same);
		     			 * e must come from p. */
		    			e = p; p = p->next; psize--;
				} else {
				    	/* First element of q is lower; e must come from q. */
		    			e = q; q = q->next; qsize--;
				}
                		/* add the next element to the merged list */
				if (tail) {
				    tail->next = e;
				} else {
				    first = e;
				}
				tail = e;
			}
			/* now p has stepped `insize' places along, and q has too */
			p = q;
        	}
		tail->next = NULL;
        	//printf("One entire Pass Complete. Number of Merges : %d \n",nmerges);
        	/* If we have done only one merge, we're finished. */
        	if (nmerges <= 1) {  /* allow for nmerges==0, the empty list case */
	    		last=tail;
            		return;
		}
        	/* Otherwise repeat, merging lists twice the size */
        	insize *= 2;
    	}
	regeneratebacklinks();
}
void linkedlist::add(char *st) {
	struct list *tmp;
	tmp = (struct list *) malloc(sizeof(struct list));
	if(tmp==NULL) {
		printf("Cannot Allocate memory for list node \n");
		printf("Error inserting : %s \n",st);
		return;
	}
	if((st[strlen(st)]=='\n'))
		st[strlen(st)]='\0';
	tmp->data=strdup(st);
	tmp->next=NULL;
	if (first==NULL) {
		first=tmp;
		last=tmp;
		tmp->prev=NULL;
	} else {
		tmp->prev=last;
		last->next=tmp;
		last=tmp;
	}
}
bool linkedlist::isEmpty(){
	return (first==NULL);
}
void linkedlist::removeAll() {
	char *tmp;
	while (!isEmpty()) {
		tmp=remove();
		if (tmp!=NULL)
			free(tmp);
	}
}

char* linkedlist::remove(){
	char *tmp;
	struct list *fs;
	if (isEmpty()) 
		return NULL;
//MBM: Using direct pointer instead of reduping	tmp = strdup(first->data);
	tmp = first->data;
	fs=first;
	if (first==last) {
		first=NULL;
		last=NULL;
	} else {
		first=first->next;
		if (first!=last )
			(first->next)->prev=first;
	}
//MBM:	free(fs->data);
	free(fs);
	return tmp;
}
char* linkedlist::getdata(){
	if(isEmpty())
		return NULL;
	return first->data;
}
void linkedlist::removekey(char *key) {
	struct list *fs;
	if (isEmpty()) 
		return;
	fs=first;
	char *tmp;
	while (fs!=NULL) {
		if (strcmp(fs->data,key)!=0) {
			fs=fs->next;
		} else {
			//printf("key found!");
			if (fs==first) {
				tmp=remove(); // remove the first guy!
				free(tmp);
				return;
			} else if (fs==last) {
				//printf("last guy\n");
				(fs->prev)->next=NULL;
				last=fs->prev;
				free(fs->data);
				free(fs);
				return;
			} else {
				//printf("middle guy\n");
				(fs->prev)->next=fs->next;
				(fs->next)->prev=fs->prev;
				free(fs->data);
				free (fs);
				return;
			}
		}
	}
}
void linkedlist::list() {
	struct list *fs;
	printf("List : ");
	if (isEmpty()) {
		printf("Empty\n");
		return;
	}
	fs=first;
	while (fs!=NULL) {
		printf("%s \n",fs->data);
		fs=fs->next;
	}
	printf("\n");
}
long linkedlist::count() {
	struct list *fs;
	long count=0;
	fs=first;
	while (fs!=NULL) {
		count++;
		fs=fs->next;
	}
	return count;
}
bool linkedlist::exists(char *key) {
	struct list *fs;
	if (isEmpty()) 
		return false;
	fs=first;
	while (fs!=NULL) {
		if (strcmp(fs->data,key)==0)
			return true;
		fs=fs->next;
	}
	return false;
}

char* linkedlist::toString() {
	return toString((char*) " ");
}

char* linkedlist::toCSVString() {
	return toString((char*)",");
}

char* linkedlist::toString(char* sep) {
	struct list *fs;
	char *tmp;
	int len;
	if (isEmpty()) 
		return NULL;
	fs=first;
	len=0;
	while (fs!=NULL) {
		len=len+1+strlen(fs->data);
		fs=fs->next;
	}
	len=len+1;
	tmp = (char*) malloc(sizeof(char)*len);
	if (tmp==NULL) {
		printf("Could not allocate memory!\n");
		return NULL;
	}
	strcpy(tmp,"");
	fs=first;
	while (fs!=NULL) {
		strcat(tmp,fs->data);
		strcat(tmp,sep);
		fs=fs->next;
	}
	return tmp;
}

linkedlist* linkedlist::copyList() {
	linkedlist* cpy;
	struct list *fs;
	cpy = new linkedlist();
	/* returning an empty list */
	if(!this)	return(cpy);
	fs = first;
	while (fs!=NULL) {
		cpy->add(fs->data);
		fs=fs->next;
	}
	return cpy;
}

linkedlist* linkedlist::minus(linkedlist *ls) {
	linkedlist *out,*tmp;
	char *ch;	
	out=copyList();
	tmp=ls->copyList();
	while (!(tmp->isEmpty())) {
		ch=tmp->remove();
		out->removekey(ch);
		free(ch);
	}
	if (tmp!=NULL)
		delete tmp;
	return out;
}
linkedlist* linkedlist::intersect(linkedlist *ls) {
	linkedlist *out,*tmp;
	char *key;

	out=new linkedlist();
	tmp=ls->copyList();
	
	while (!(tmp->isEmpty())) {
		key=tmp->remove();
		if (exists(key))
			out->add(key);
		free(key);
	}
	delete tmp;
	return out;
}

void linkedlist::removeDuplicates() {
	sort();
	struct list *t,*tmp;
	t=first;
	while (t!=NULL) {
		if (t->next!=NULL) {
			if((strcmp(t->data,t->next->data)==0)) {
				tmp=t->next;
				t->next=tmp->next;
				free (tmp->data);
				free(tmp);
			} else 
				t=t->next;
		} else
			t=t->next;
	}
	regeneratebacklinks();
}
void linkedlist::merge(linkedlist *ls) {
/*	if (first==NULL) 
		first=ls->first;
	else 
		last->next=ls->first;
 	last = ls->last;	
*/
	linkedlist *tmp;
	char *ch;
	tmp=ls->copyList();
	while(!(tmp->isEmpty())) {
		ch=tmp->remove();
		add(ch);
		free(ch);
	}
	delete tmp;
}
void linkedlist::selfminus(linkedlist *ls) {
	linkedlist *tmp;
	tmp=ls->copyList();
	while (!(tmp->isEmpty())) {
		removekey(tmp->remove());
	}
	delete tmp;
}

void linkedlist::selfintersect(linkedlist *ls) {
	// Assumes sorted inputs
	linkedlist *tmp;
	struct list *curr1,*curr2,*prev,*tm;
	int cmp;
	tmp=ls->copyList();
        curr1=first;
	curr2=tmp->first;
	prev=NULL;	
	first=NULL;
	while ((curr1) && (curr2)) {
		if (curr1==NULL)
			return;
		if (curr2==NULL)
			return;
		cmp=strcmp(curr1->data,curr2->data);
//		printf("Comparing %s and %s : %d \n",curr1->data,curr2->data,cmp);
		if (cmp==0) {
			if (prev==NULL)
				first=curr1;
			prev=curr1;
//			printf("Storing %s \n",curr1->data);
			curr1=curr1->next;
			curr2=curr2->next;
		} else if (cmp<0) {
			while(strcmp(curr1->data,curr2->data)<0) {
				tm=curr1;
				if (prev!=NULL) {
					prev->next=curr1->next;
					curr1=prev->next;
				} else 
					curr1=curr1->next;
				free (tm->data);
				free( tm);
				if (curr1==NULL)
					  break;
			}
		} else {
			while(strcmp(curr1->data,curr2->data)>0) {
				curr2=curr2->next;
				if (curr2==NULL)
					break;
			}
		}
		if (curr2==NULL) {
//			printf("End of List 2\n");
			if (prev!=NULL) {
				prev->next=NULL;
				last=prev;
			} 
			while (curr1!=NULL) {
				tm=curr1;
				curr1=curr1->next;
				free (tm->data);
				free( tm);
			}
//			printf("Intersection over\n");

			return;
		}
		if (curr1==NULL) {
/*			printf("End of List 1\n");
			if (prev==NULL) 
				printf("Prev null\n");
			if (last==NULL) 
				printf("last null\n"); */
			if (prev!=NULL)
				last=prev;
//			printf("Intersection over\n");
			return;
		}
	}
	regeneratebacklinks();
}


void linkedlist::sortedselfunion(linkedlist *ls) {
	linkedlist *out,*cpy;
 	struct list *curr1,*curr2,*tm;
	out = new linkedlist();	
	curr1=first;
	curr2=ls->first;
	while ((curr1) && (curr2)){
		if (strcmp(curr1->data,curr2->data)<=0) {
			if (out->isEmpty()) {
					out->add(curr1->data);
			} else if (strcmp(out->last->data,curr1->data)!=0)
					out->add(curr1->data);
			if (strcmp(curr1->data,curr2->data)==0)
				curr2=curr2->next;
			curr1=curr1->next;
		} else {
			if (out->isEmpty()) {
				out->add(curr2->data);
			} else if (strcmp(out->last->data,curr2->data)!=0)
				out->add(curr2->data);
			curr2=curr2->next;
		}
	}
	while (curr1) {
		out->add(curr1->data);
		curr1=curr1->next;
	}
	while (curr2) {
		out->add(curr2->data);
		curr2=curr2->next;
	}
	removeAll();
	char *ch;
	while(!(out->isEmpty())) {
		ch=out->remove();
		add(ch);
		free(ch);
	}
}
void linkedlist::sortedselfminus(linkedlist *ls) {
	// Assumes sorted inputs
	linkedlist *tmp;
	struct list *curr1,*curr2,*prev,*tm;
	int cmp;
	if ((ls==NULL) || (ls->isEmpty()))
		return;
	tmp=ls->copyList();
        curr1=first;
	curr2=tmp->first;
	prev=NULL;
	first=NULL;	
	while ((curr1) && (curr2)) {
		cmp=strcmp(curr1->data,curr2->data);
		if (cmp==0) {
			tm = curr1;
			curr1=curr1->next;
			curr2=curr2->next;
			free (tm->data);
			free (tm);
		} else if (cmp<0) {
			while(strcmp(curr1->data,curr2->data)<0) {
				if (prev!=NULL) {
					prev->next=curr1;
					prev=curr1;
					curr1=curr1->next;
				} else  {
					first=curr1;
					prev=first;
					curr1=curr1->next;
				}
				if (curr1==NULL)
					  break;
			}
		} else {
			while(strcmp(curr1->data,curr2->data)>0) {
				curr2=curr2->next;
				if (curr2==NULL)
					break;
			}
		}
	}
	if (curr2==NULL) {
		while(curr1) {
			if (prev!=NULL) {
				prev->next=curr1;
				prev=curr1;
				curr1=curr1->next;
			} else {
				first=curr1;
				prev=first;
				curr1=curr1->next;
			}
		}
	}
	if (prev!=NULL) {
		prev->next=NULL;
		last=prev;
	}
	delete tmp;
        regeneratebacklinks();	
}

/*
 *  Before Sorting
 
void linkedlist::selfintersect(linkedlist *ls) {
	linkedlist *out,*tmp;
	char *key;

	out=new linkedlist();
	tmp=ls->copyList();
	
	while (!(tmp->isEmpty())) {
		key=tmp->remove();
		if (exists(key))
			out->add(key);
	}
	delete tmp;
	removeAll();
	while (!(out->isEmpty())) 
		add(out->remove());
	delete out;
}
*/


bool beginsWith(char* src, char* substr){
	if (strlen(substr)>strlen(src))
		return false;
	int i;
	for (i=0;i<strlen(substr);i++)
		if (src[i]!=substr[i])
			return false;

	return true;
}

bool linkedlist::saveToFile() {
	linkedlist* cpy;
	struct list *fs;
	cpy = new linkedlist();

	FILE *fp=fopen("temp.text", "w+");

	/* returning an empty list */
	if(!this)	return true;
	fs = first;
	while (fs!=NULL) {
		fwrite(fs->data, strlen(fs->data)+1, 1, fp);
		fs=fs->next;
	}

	return true;
}

